[2018NOI导刊]B君的病症

发表于 | 分类于 ， | | 阅读次数:

题目

题目描述

享国之日浅，国家无事。
B 君看到了 Z 君的第二题，觉得很难。 于是自己出了一个简单题。 大 A 是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现在有 n 种颜色，其中第 i 种颜色的珠子有 ai 个。要求排列中第 i 种颜色珠子的所有珠子，一定要排在第 i + 1 种颜色的第一个和最后一个珠子之间。问有多少种排列珠子的方案，因为方案数会很大，所以请输出答案对1000000007 取模之后的结果。

输入格式

第一行一个整数 n。 以下 n 行，每行一个整数 ai。

输出格式

一行一个整数表示答案。

输入样例

1
2
3
4
3
2
4
4

输出样例

1
168

说明

对于 100% 的数据，满足 1 ≤ n ≤ 10^4 , 2 ≤ ai ≤ 15。 对于 70% 的数据，满足 1 ≤ n ≤ 10^2。

题解

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstdio>
#include<iostream>
using namespace std;
#define MOD 1000000007
#define MAXN 100001
long long fact[MAXN],inv[MAXN];

long long pow(long long a,long long b){
	long long ans=1;
	while(b){
		if(b&1)ans=a*ans%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans%MOD;
}

long long c(long long m,long long n){
	return fact[m]*inv[n]%MOD*inv[m-n]%MOD;
}

void pre(){
	fact[0]=1;
	inv[0]=1;
	for(int i=1;i<MAXN;i++){
		fact[i]=fact[i-1]*i%MOD;
		inv[i]=pow(fact[i],MOD-2);
	}
}

int main(){
	long long x,y;
	pre();
	cin>>x;
	long long z=1;
	int s=0;
	for(int i=1;i<=x;i++){
		scanf("%lld",&y);
		z=z*c(s+y-2,y-2)%MOD;
		s+=y;
	}
	cout<<z;
	return 0;
}